Agglomerative Clustering

계층적 군집화는 데이터 포인트들 사이의 계층적 관계를 트리 구조로 만들어내는 군집 분석 기법이다. 이 방법은 크게 병합적 접근법과 분할적 접근법으로 나뉘는데, Agglomerative Clustering은 병합적 접근법에 해당한다. 이는 데이터의 자연스러운 계층 구조를 발견하고자 할 때 유용하며, 군집의 개수를 사전에 지정할 필요가 없다는 특징을 가진다.

이 방법의 핵심 출력물은 덴드로그램이다. 덴드로그램은 병합 과정을 시각적으로 보여주는 트리 다이어그램으로, 데이터 포인트들이 어떤 순서와 거리(또는 유사도)로 결합되어 최종적인 하나의 군집을 형성하는지를 보여준다. 분석자는 이 덴드로그램을 보고 적절한 군집 개수를 결정할 수 있다.

계층적 군집화는 유전자 발현 분석, 문서 분류, 사회 네트워크 분석 등 다양한 분야에서 활용된다. 특히 데이터 내부에 존재하는 중첩된 그룹 구조나 계층을 탐색하는 데 강점을 보인다. 그러나 모든 데이터 포인트 쌍 간의 거리를 계산해야 하므로 대규모 데이터셋에 적용할 때는 계산 비용이 높아질 수 있다는 한계가 있다.

병합적 접근법은 계층적 군집화를 수행하는 두 가지 주요 전략 중 하나로, 하향식 또는 집합적 방식으로도 불린다. 이 방법은 각각의 데이터 포인트를 하나의 독립된 군집으로 취급하는 것에서 시작한다. 알고리즘은 초기 단계에서 군집의 수가 데이터 포인트의 수와 동일한 상태이며, 이후 단계마다 가장 유사하거나 거리가 가까운 두 군집을 찾아 하나로 합치는 과정을 반복한다. 이 반복적인 병합 과정은 모든 데이터가 최종적으로 하나의 거대한 군집으로 통합될 때까지 계속되어, 데이터 간의 전체적인 계층 구조를 만들어낸다.

이 접근법의 핵심은 매 단계에서 어떤 두 군집을 병합할지 결정하는 규칙, 즉 연결 기준에 있다. 연결 기준은 군집 간의 거리 또는 유사도를 정의하는 방법으로, 단일 연결, 완전 연결, 평균 연결, 와드 연결 등 다양한 방식이 존재한다. 예를 들어, 단일 연결은 두 군집 내 가장 가까운 두 점 사이의 거리를, 완전 연결은 가장 먼 두 점 사이의 거리를 군집 간 거리로 삼는다. 이러한 기준 선택은 최종 군집 구조의 형태와 특성에 직접적인 영향을 미친다.

병합 과정의 전체 이력은 덴드로그램이라는 트리 형태의 다이어그램으로 시각화된다. 덴드로그램의 수평축은 데이터 포인트들을, 수직축은 군집이 병합되는 거리(또는 비유사도)를 나타낸다. 사용자는 이 덴드로그램을 분석하여 데이터의 자연스러운 군집 수준을 파악하고, 원하는 군집 수에 해당하는 높이에서 트리를 절단함으로써 최종 군집 할당 결과를 얻을 수 있다. 따라서 병합적 군집화는 군집의 수를 사전에 지정해야 하는 K-평균 군집화와 달리, 사전 지식 없이도 데이터가 가진 계층적 관계를 탐색하고 유연하게 결과를 도출할 수 있는 장점을 가진다.

병합적 군집화의 첫 번째 핵심 단계는 모든 데이터 포인트 간의 유사도 또는 거리를 정량화하는 것이다. 이를 위해 유클리드 거리, 맨해튼 거리, 코사인 유사도 등 다양한 척도를 사용할 수 있으며, 선택된 척도에 따라 군집화 결과가 달라질 수 있다. 이 계산 결과는 일반적으로 대칭 행렬 형태의 거리 행렬로 저장되며, 행렬의 각 요소는 두 데이터 포인트 간의 거리 값을 나타낸다.

초기에는 각 데이터 포인트가 하나의 군집으로 간주되므로, 이 거리 행렬은 개별 포인트 간의 거리를 담고 있다. 알고리즘이 진행되면서 군집이 병합될 때마다, 새로 형성된 군집과 다른 군집들 간의 거리를 다시 계산해야 한다. 이때 어떤 방법으로 군집 간 거리를 정의할지 결정하는 것이 바로 연결 기준이다. 따라서 거리 행렬은 알고리즘의 각 반복 단계에서 갱신되는 동적인 정보 저장소 역할을 한다.

거리 행렬의 계산은 알고리즘의 계산 복잡도에 직접적인 영향을 미친다. N개의 데이터 포인트가 있을 때, 모든 쌍 간의 거리를 계산하는 데 필요한 시간 복잡도는 일반적으로 O(N^2)에 달한다. 이는 대규모 데이터셋에 병합적 군집화를 적용할 때 주요한 계산 부담으로 작용한다. 효율적인 구현을 위해서는 거리 행렬을 한 번 계산하여 저장해두고, 군집 병합 시 필요한 부분만 업데이트하는 전략이 사용되기도 한다.

병합 알고리즘의 핵심은 연결 기준이다. 연결 기준은 병합 과정에서 두 군집 간의 거리 또는 유사도를 어떻게 정의하고 계산할지를 결정하는 규칙이다. 이 기준에 따라 군집의 형태와 특성이 크게 달라지기 때문에, 데이터의 특성과 분석 목적에 맞는 연결 기준을 선택하는 것이 매우 중요하다.

주요 연결 기준으로는 단일 연결, 완전 연결, 평균 연결, 와드 연결 등이 널리 사용된다. 단일 연결은 두 군집 내 가장 가까운 두 점 사이의 거리를 군집 간 거리로 삼으며, 이는 체인 형태의 군집을 생성하는 경향이 있다. 완전 연결은 반대로 두 군집 내 가장 먼 두 점 사이의 거리를 사용하여 조밀하고 컴팩트한 군집을 형성한다. 평균 연결은 두 군집 내 모든 점 쌍 간 거리의 평균값을 계산하는 방식으로, 앞의 두 방법의 절충적 특성을 가진다.

와드 연결은 다른 기준들과 차별화된다. 이 방법은 두 군집을 병합했을 때 발생하는 분산의 증가량을 거리로 정의한다. 즉, 군집 내 데이터의 응집도를 최대화하는 방향으로 병합을 진행하여, 일반적으로 크기가 비슷하고 구형에 가까운 군집을 만들어내는 경향이 있다. 이는 K-평균 군집화의 목표와 유사한 측면이 있다.

따라서, 병합적 군집화를 수행할 때는 데이터의 분포와 분석가가 원하는 군집의 특성을 고려하여 적절한 연결 기준을 선택해야 한다. 예를 들어, 비구형의 복잡한 형태를 가진 군집을 탐지하려면 단일 연결이 유용할 수 있지만, 노이즈에 민감하다는 단점이 있다. 반면, 와드 방법은 안정적인 결과를 제공하지만, 군집의 크기가 균일할 것이라는 가정이 전제된다.

단일 연결은 계층적 군집화에서 사용되는 가장 기본적인 연결 기준 중 하나이다. 이 방법은 두 군집 사이의 거리를 각 군집에 속한 모든 데이터 포인트 쌍의 거리 중에서 가장 가까운, 즉 최소 거리로 정의한다. 다른 말로 최소 거리법 또는 최근접 이웃법이라고도 부른다.

구체적으로, 두 군집 A와 B가 있을 때, 군집 A의 모든 점과 군집 B의 모든 점 사이의 유클리드 거리나 다른 거리 척도를 계산한다. 단일 연결 알고리즘은 이 모든 쌍의 거리 값 중 가장 작은 값을 두 군집 간의 거리로 채택한다. 이 거리 값을 기준으로 가장 가까운 두 군집을 찾아 병합하는 과정을 반복한다.

이러한 정의로 인해 단일 연결은 군집이 길쭉한 형태나 체인 형태로 늘어나는 경향이 있다. 서로 다른 군집이라도 그 사이를 가로지르는 일부 데이터 포인트들이 가까이 위치하면, 이들을 연결하는 다리 역할을 하여 먼 거리에 있는 군집들도 빠르게 하나로 묶일 수 있다. 이는 군집의 응집도를 유지하기보다는 데이터 공간에서의 연결성에 더 초점을 맞춘 결과이다.

따라서 단일 연결은 잡음이나 이상치에 민감할 수 있으며, 군집의 경계가 모호해지는 단점이 있다. 하지만 계산이 비교적 간단하고, 비구형 또는 복잡한 형태의 군집을 발견하는 데 유용할 수 있다. 특히 덴드로그램을 통해 데이터 포인트들이 어떻게 서로 연결되어 있는지의 계층적 구조를 파악하는 데 자주 활용된다.

완전 연결은 계층적 군집화에서 군집 간 거리를 정의하는 주요 연결 기준 중 하나이다. 이 방법은 두 군집 사이의 거리를, 각 군집에 속한 모든 데이터 포인트 쌍의 거리 중 가장 먼 거리로 계산한다. 즉, 한 군집의 어떤 점과 다른 군집의 어떤 점 사이의 최대 거리를 두 군집 간의 거리로 삼는다. 이는 군집을 병합할 때, 두 군집 내 가장 멀리 떨어진 점들까지도 고려하여 매우 조밀한 군집을 형성하도록 유도하는 특성을 가진다.

이러한 정의 때문에 완전 연결은 종종 최대 연결 또는 최장 거리법이라고도 불린다. 이 방법은 군집의 형태에 민감하게 반응하여, 군집 내 모든 점들이 서로 비교적 가까울 때만 병합을 허용하는 경향이 있다. 결과적으로 생성되는 군집들은 일반적으로 매우 조밀하고 구형에 가까운 형태를 띠게 된다. 이는 군집 간의 경계가 뚜렷하게 구분되는 결과를 만들어내는 데 기여한다.

완전 연결의 주요 단점은 잡음과 이상치에 매우 취약하다는 점이다. 두 군집이 대체로 가까이 위치해 있더라도, 단 하나의 이상치나 잡음 포인트가 멀리 떨어져 있다면, 그 최대 거리가 군집 간 거리로 계산되어 병합이 지연되거나 원치 않는 군집 구조가 형성될 수 있다. 또한, 군집의 크기가 커질수록 최대 거리를 계산하는 데 필요한 계산 비용이 증가할 수 있다.

이 방법은 군집의 내부 응집도를 중시하는 응용 분야, 예를 들어 유전자 발현 데이터 분석이나 문서 군집화에서 특정 주제를 명확히 구분하고자 할 때 유용하게 활용된다. 완전 연결은 단일 연결이 만들어내는 길쭉한 체인 형태의 군집을 방지하는 대신, 상대적으로 더 작고 조밀한 군집들을 생성한다는 점에서 대비된다.

평균 연결은 계층적 군집화에서 군집 간의 거리를 계산하는 주요 연결 방법 중 하나이다. 이 방법은 두 군집 사이의 모든 데이터 포인트 쌍 간의 거리를 계산한 후, 그 거리들의 평균값을 두 군집 간의 거리로 정의한다. 즉, 군집 A의 모든 점과 군집 B의 모든 점 사이의 거리를 모두 구하여 산술 평균을 낸 값이 두 군집의 유사도가 된다. 이는 단일 연결이나 완전 연결과 달리, 모든 데이터 포인트 쌍의 정보를 종합적으로 반영한다는 특징이 있다.

이 접근법은 군집의 크기나 형태에 비교적 덜 민감한 편이며, 군집 간의 전반적인 평균적 유사성을 기준으로 병합을 진행한다. 따라서 단일 연결이 가질 수 있는 체인 현상(한 군집이 길게 늘어지는 현상)을 완화하고, 완전 연결이 가질 수 있는 과도하게 컴팩트한 군집을 형성하는 경향을 조절하는 효과가 있다. 결과적으로 평균 연결은 보다 균형 잡힌 군집 구조를 생성하는 데 기여한다.

평균 연결은 계산 비용이 다른 방법들에 비해 다소 높은 편이다. 매 병합 단계마다 두 군집에 속한 모든 점들 사이의 거리를 계산해야 하기 때문이다. 그러나 이는 군집의 전체적인 분포를 잘 반영한 거리 척도를 제공한다는 장점으로 이어진다. 이 방법은 생물정보학에서 유전자 발현 데이터의 군집화나, 문서 군집화, 시장 세분화와 같은 다양한 분야에서 활용된다.

실제 구현에서는 계산 효율성을 위해 다양한 최적화 기법이 적용되기도 한다. 평균 연결은 계층적 군집화의 덴드로그램을 생성할 때, 군집 병합의 높이(거리)를 결정하는 기준으로 사용되며, 최종적으로 사용자가 원하는 군집 수를 덴드로그램을 잘라서 선택할 수 있게 한다.

와드 연결은 계층적 군집화에서 군집을 병합할 때 사용되는 연결 기준 중 하나로, 병합 후 군집 내 분산의 증가량을 최소화하는 방향으로 군집을 합치는 방법이다. 이 방법은 군집 내 데이터 포인트들이 서로 얼마나 응집되어 있는지를 중요하게 고려하며, 병합으로 인해 군집 내부의 응집도가 크게 흐트러지지 않도록 설계되었다. 따라서 생성된 군집들은 일반적으로 크기가 비슷하고 구형에 가까운 형태를 띠는 경향이 있다.

와드 연결의 핵심은 병합 후의 총 분산을 계산하는 것이다. 알고리즘은 모든 가능한 군집 쌍을 고려하여, 두 군집을 병합했을 때 발생하는 군집 내 오차 제곱합의 증가량을 계산한다. 이 증가량은 본질적으로 두 군집의 중심 간 유클리드 거리의 제곱에 두 군집의 크기를 가중치로 곱한 값과 비례한다. 알고리즘은 이 증가량이 가장 작은, 즉 군집 내 응집도를 가장 잘 유지하는 두 군집을 선택하여 병합한다.

이 방법은 다른 연결 기준에 비해 계산량이 많지만, 군집의 크기와 형태를 균일하게 만드는 데 효과적이다. 이러한 특성 때문에 와드 연결은 K-평균 군집화와 유사한 구형의 군집을 생성하는 것으로 알려져 있다. 실제 응용에서는 유전자 발현 분석, 시장 세분화, 이미지 분할 등 군집의 응집도를 중요한 기준으로 삼는 다양한 분야에서 활용된다.

와드 연결의 주요 단점은 군집 내 분산에 민감하게 반응하기 때문에 이상치의 영향을 크게 받을 수 있다는 점이다. 또한 계산 복잡도가 높아 대규모 데이터셋에는 적용하기 어려울 수 있다. 그럼에도 불구하고, 군집의 구조를 명확하고 균일하게 정의해야 하는 경우에는 여전히 널리 사용되는 방법이다.

병합적 군집화의 가장 큰 장점은 군집의 개수를 사전에 지정할 필요가 없다는 점이다. K-평균 군집화와 같은 방법은 군집 수 K를 사용자가 미리 정해야 하지만, 병합적 군집화는 모든 데이터 포인트를 개별 군집으로 시작하여 단계적으로 병합해 나가므로, 최종적으로 생성되는 덴드로그램을 통해 다양한 수준의 군집 구조를 한 번에 살펴볼 수 있다. 이는 데이터에 대한 사전 지식이 부족할 때 유용하며, 사용자는 덴드로그램을 분석하여 데이터에 가장 적합한 군집 수를 사후적으로 결정할 수 있다.

또한, 이 방법은 데이터 포인트 간의 계층적 관계를 명확하게 보여준다. 덴드로그램은 군집이 병합되는 순서와 각 병합 시점의 거리(또는 유사도)를 시각적으로 표현하므로, 어떤 하위 군집들이 모여 더 큰 상위 군집을 형성하는지, 그리고 군집 간의 상대적 유사도는 어느 정도인지를 직관적으로 이해할 수 있게 해준다. 이는 생물정보학에서의 계통수 작성이나 문서의 토픽 모델링과 같이 계층 구조가 중요한 분야에서 특히 유용하게 활용된다.

마지막으로, 다양한 연결 기준을 선택할 수 있어 데이터의 특성에 맞게 알고리즘의 동작을 조정할 수 있다. 예를 들어, 단일 연결 방법은 체인 효과에 민감하지만 비구형 군집을 잘 찾을 수 있고, 완전 연결 방법은 컴팩트한 군집을 형성하는 데 강점이 있다. 와드 연결 방법은 군집 내 분산을 최소화하는 방식으로 동작하여 일반적으로 균형 잡힌 군집을 생성하는 것으로 알려져 있다. 이러한 유연성 덕분에 사용자는 문제의 맥락과 데이터의 성격에 가장 적합한 거리 계산 방식을 선택하여 적용할 수 있다.

병합적 군집화는 계산 비용이 높다는 단점이 있다. 모든 데이터 포인트 쌍 간의 거리를 계산하여 거리 행렬을 구성하고, 각 병합 단계마다 이 행렬을 갱신해야 하기 때문에, 데이터 포인트 수가 N개일 때 일반적인 시간 복잡도는 O(N^3)에 달한다. 이는 대규모 데이터셋에 적용하기에는 비효율적이며, K-평균 군집화나 DBSCAN과 같은 다른 군집화 알고리즘에 비해 확장성이 떨어진다.

또한, 알고리즘이 결정론적이며 한 번 병합이 이루어지면 이전 단계로 되돌릴 수 없다는 점도 한계로 지적된다. 이는 초반의 병합 결정이 최종 군집 구조에 큰 영향을 미치게 만든다. 만약 초기 단계에서 노이즈나 이상치에 의해 잘못된 병합이 발생하면, 그 오류가 이후 모든 병합 과정에 전파되어 최종 결과를 왜곡시킬 수 있다.

마지막으로, 대부분의 연결 방법은 군집의 모양에 대한 사전 가정을 내포하고 있어 특정 형태의 군집만 잘 찾는 경향이 있다. 예를 들어, 단일 연결 방법은 체인 효과로 인해 길쭉한 군집을 생성하기 쉬우며, 완전 연결 방법은 구형에 가까운 컴팩트한 군집을 선호한다. 따라서 데이터의 실제 군집 구조가 알고리즘의 내재적 가정과 맞지 않을 경우 성능이 저하될 수 있다.

덴드로그램은 계층적 군집화 과정의 결과를 시각적으로 표현한 트리 형태의 다이어그램이다. 이는 병합적 군집화 알고리즘이 데이터 포인트들을 단계적으로 어떻게 병합해 나가는지를 보여주며, 데이터의 계층적 구조를 한눈에 파악할 수 있게 한다.

덴드로그램의 수직 축은 일반적으로 군집 간의 거리 또는 비유사도를 나타낸다. 트리의 맨 아래쪽 잎 노드는 각각의 개별 데이터 포인트에 해당한다. 알고리즘이 진행되면서 두 군집이 병합될 때마다, 두 군집을 연결하는 수평선이 그려지고, 이 수평선의 높이는 해당 병합이 일어난 시점의 군집 간 거리에 비례한다. 따라서 거리가 가까운 군집일수록 낮은 높이에서 병합된 것으로 표시된다.

이 시각화의 가장 큰 장점은 최종 군집 수를 사전에 지정하지 않고도 데이터를 분석할 수 있다는 점이다. 분석자는 덴드로그램을 보고 수직 축을 특정 거리(또는 높이)에서 가로로 잘라서 원하는 수준의 군집 구성을 결정할 수 있다. 예를 들어, 긴 수직 간격을 가로지르는 선을 그으면, 그 선과 교차하는 수직선의 개수가 그 시점의 군집 개수가 된다. 이를 통해 데이터의 자연스러운 군집 구조를 탐색적으로 발견하는 데 유용하다.

덴드로그램은 생물정보학에서 유전자 발현 패턴 분석이나 계통학에서 종 간의 진화적 관계를 나타내는 데 널리 사용된다. 또한, 문서 군집화나 이미지 분할과 같은 다양한 패턴 인식 작업에서 데이터의 내재된 계층을 이해하는 도구로 활용된다.

K-평균 군집화는 사전에 군집의 개수 K를 지정해야 하는 분할 군집화 방법이다. 이 방법은 각 군집의 중심점인 센트로이드를 기준으로 데이터를 할당하며, 중심점의 위치를 반복적으로 업데이트하여 군집을 최적화한다. Agglomerative Clustering과 달리 계층 구조를 생성하지 않고, 주어진 K값에 대해 평평한 군집 할당 결과를 제공한다.

K-평균 군집화의 작동 과정은 먼저 K개의 초기 중심점을 임의로 설정하는 것으로 시작한다. 그 후, 각 데이터 포인트를 가장 가까운 중심점이 속한 군집에 할당하고, 각 군집에 속한 데이터 포인트들의 평균을 계산하여 새로운 중심점으로 업데이트한다. 이 할당과 업데이트 과정은 중심점의 이동이 없을 때까지 반복된다.

Agglomerative Clustering과 비교했을 때, K-평균 군집화의 가장 큰 차이점은 군집의 계층적 구조를 보여주지 않으며, 군집의 수를 사용자가 미리 정해야 한다는 점이다. 또한, 초기 중심점의 선택에 민감하여 다른 결과를 낳을 수 있고, 군집의 크기나 밀도가 균일하지 않거나 원형이 아닌 형태의 군집을 찾는 데는 한계가 있다.

따라서 데이터의 계층적 관계를 분석하고 싶거나 적절한 군집 수를 모를 때는 Agglomerative Clustering이 유용하며, 계산 효율성이 중요하고 군집 수가 명확한 대규모 데이터셋에는 K-평균 군집화가 더 널리 사용된다.

DBSCAN은 밀도 기반의 대표적인 군집화 알고리즘이다. 이 방법은 K-평균 군집화나 계층적 군집화와 달리 군집의 개수를 사전에 지정할 필요가 없으며, 임의의 형태를 가진 군집을 발견할 수 있다는 장점이 있다. 또한 잡음 데이터나 이상치를 효과적으로 식별하여 별도의 군집으로 분리할 수 있다.

DBSCAN의 핵심 작동 원리는 두 가지 매개변수, 즉 반경 엡실론과 최소 포인트 수 MinPts에 기반한다. 알고리즘은 각 데이터 포인트를 중심으로 엡실론 반경 내에 MinPts 개 이상의 다른 포인트가 존재하면 해당 포인트를 핵심 포인트로 정의한다. 핵심 포인트의 주변에 밀집된 포인트들은 동일한 군집으로 확장되어 나간다. 반면, 핵심 포인트가 아니면서 다른 군집의 엡실론 내에도 속하지 않는 포인트는 잡음으로 간주된다.

Agglomerative Clustering과 DBSCAN의 주요 차이점은 군집 형성 방식에 있다. Agglomerative Clustering은 모든 데이터 포인트 간의 거리 행렬을 기반으로 계층적 관계를 형성하는 반면, DBSCAN은 데이터 공간의 지역적 밀도에 주목한다. 따라서 DBSCAN은 서로 다른 밀도를 가진 군집을 구분하는 데 유리하지만, 밀도가 균일하지 않은 데이터셋에서는 파라미터 설정이 어려울 수 있다.

이 알고리즘은 공간 데이터베이스, 이미지 분할, 이상 탐지 등 다양한 분야에서 활용된다. 특히 지리 정보 시스템에서 서로 가깝게 모여 있는 지점들을 군집화하거나, 센서 네트워크 데이터에서 정상 패턴과 다른 이상 신호를 찾는 데 적합하다.